/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-break
   @Language: C++
   @Datetime: 19-03-22 12:33
   */


// Method 1 Backtracking, Time O(n^2), Space O(1), Time 386ms
class Solution {
	bool flag;
	int min, max;
	void core(string &s, int i, int l, unordered_set<string> &dict){
		if(i+l>s.length() || l>max || flag) return;
		if(dict.find(s.substr(i,l))!=dict.end()){
			if (i+l==s.length()) flag=true;
			core(s,i+l,min,dict);
		}
		core(s,i,l+1,dict);
	}
public:
	/*
	 * @param s: A string
	 * @param dict: A dictionary of words dict
	 * @return: A boolean
	 */
	bool wordBreak(string &s, unordered_set<string> &dict) {
		// write your code here
		if (s.length()<1) return true;
		min=INT_MAX, max=0;
		for(const auto &word:dict){
			min=min<word.length()?min:word.length();
			max=max>word.length()?max:word.length();
		}
		flag=false;
		core(s,0,min,dict);
		return flag;
	}
};


// Method 2 DP, Time O(n*l^2), Space O(n), Time 814ms
class Solution {
public:
	/*
	 * @param s: A string
	 * @param dict: A dictionary of words dict
	 * @return: A boolean
	 * Tip:
	 * dp[i] means A[0~i] if can break
	 */
	bool wordBreak(string &s, unordered_set<string> &dict) {
		// write your code here
		vector<bool> dp(s.length(),false);
		dp[0]=true;
		int maxlen=0, minlen=INT_MAX;
		for(const auto &word:dict){
			maxlen=maxlen>word.length()?maxlen:word.length();
			minlen=minlen<word.length()?minlen:word.length();
		}
		for(int i=1; i<=s.length(); ++i){
			for(int l=minlen; l<=i && l<=maxlen && !dp[i]; ++l){
				if (dp[i-l] && dict.count(s.substr(i-l,l))) dp[i]=true;
			}
		}
		return dp[s.length()];
	}
};


// Method 3 DP, Time O(n*k), Space O(n+k), Time 294ms
class Solution {
public:
	/*
	 * @param s: A string
	 * @param dict: A dictionary of words dict
	 * @return: A boolean
	 * Tip:
	 * dp[i] means A[0~i] if can break
	 */
	bool wordBreak(string &s, unordered_set<string> &dict) {
		// write your code here
		vector<bool> dp(s.length(),false);
		dp[0]=true;
		unordered_set<int> len;
		for(const auto &word:dict){
			len.insert(word.length());
		}
		for(int i=1; i<=s.length(); ++i){
			for(const auto &l:len){
				if (i>=l && dp[i-l] && dict.count(s.substr(i-l,l))){
					dp[i]=true;
					break;
				}
			}
		}
		return dp[s.length()];
	}
};
